#include <stdio.h>
#include <iostream.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#define so_canh_toida 100
typedef struct {
	int dau;
	int cuoi;
	int trongso;
} canh;
typedef struct {
	int sodinh;
	int tdinh[100];
	int socanh;
	canh dscanh[so_canh_toida];
} dothi;
void nhap_do_thi(dothi &dt)
//doc noi dung file va dua vao do thi

{
	char str1[255];
	FILE *fb = fopen("graph.txt","rt");
	if (fb == NULL) {
		printf("Mo file ko thanh cong");
		return;
	}
	fscanf(fb,"%d%d", &dt.sodinh,&dt.socanh);

	//tao ten cua cac dinh trong do thi
	for(int j=0;j<dt.sodinh;j++)
	{
		dt.tdinh[j] = j+1;
	}

	for (int i=0;i<dt.socanh;i++)
	{
		fscanf(fb,"%d%d%d",&dt.dscanh[i].dau,&dt.dscanh[i].cuoi,&dt.dscanh[i].trongso);
	}
	
}
void in_do_thi(dothi dt)
{
	cout<<"so dinh cua do thi: "<<dt.sodinh<<endl;
	cout<<"so canh cua do thi: "<<dt.socanh<<endl;
	cout<<"Tap cac dinh cua do thi: { ";
	for(int i=0;i<dt.sodinh;i++) cout<<dt.tdinh[i]<<" ";
	cout<<"}"<<endl;
	cout<<"Tap cac canh cua do thi: "<<endl;
	for(int i=0;i<dt.socanh;i++)
	{
		cout<<"canh "<<i+1<<": "<<dt.dscanh[i].dau<<"  "<<dt.dscanh[i].cuoi<<"  ";
		cout<<dt.dscanh[i].trongso<<endl;
	}
}
int tong_tso(dothi G)
{
	int tam = 0;
	for(int i=0;i<G.socanh;i++) tam += G.dscanh[i].trongso;
	return tam;
}
int tim_dinh(dothi T, int dinh) //tim dinh da co trong T hay chua. Neu co tra ve true
{
	int i=0;
	while ((i<T.sodinh)&&(T.tdinh[i] != dinh)) i++;
	return (i<T.sodinh);
}
dothi tao_tap_canh_M(dothi G, dothi T) //tra ve canh co trong so min co dinh dau thuoc T va dinh cuoi ko thuoc T
{
	dothi M;
	M.socanh = 0; //khoi tao tap canh M ban dau rong
	for (int i=0; i<T.sodinh; i++)
	{
		for(int j=0;j<G.socanh;j++)
		{
			if ((G.dscanh[j].dau == T.tdinh[i])&&(!tim_dinh(T,G.dscanh[j].cuoi)))
			{
				M.dscanh[M.socanh++] = G.dscanh[j];
			}		
		}
	}
	return M;
}
canh tim_canh_min(dothi M)
{
	canh tam= M.dscanh[0];;
	int ts_min = M.dscanh[0].trongso;
		
	for (int i=1; i<M.socanh&&ts_min > M.dscanh[i].trongso; i++) 
		{
			ts_min = M.dscanh[i].trongso;
			tam= M.dscanh[i];	
		}
	return tam;	
}
void them_canh_vao_T(dothi &T, canh a)// them canh a vao do thi T va dinh moi vao tap dinh cua T
{
	
	//them canh vao T
	T.dscanh[T.socanh++]= a;
	//them dinh moi vao tap dinh cua T
	T.tdinh[T.sodinh++] = a.cuoi;
}
int tt_prim(dothi G, dothi &T) // ham tra ve 0 neu do thi ko lien thong
{
	dothi M;
	//khoi tao cay khung T ban dau
	T.sodinh = 1;//so dinh cua T ban dau la 1 dinh
	T.tdinh[0]=1; //dinh dau tien cua T co ten la 1
	T.socanh = 0;
	canh tam;
	do{
		M = tao_tap_canh_M(G, T);
		if (M.socanh==0) return 0; //Neu tap M rong: dung va ket luan do thi ko lien thong
		tam = tim_canh_min(M);//tim canh min trong M
		them_canh_vao_T(T, tam); //them canh min vua tim vao T
		//cout<<"so dinh cua T: "<<T.sodinh<<endl;
	}while (T.socanh < G.sodinh-1);
	
	return 1;
}

int main()
{
    dothi G,T;
    nhap_do_thi(G);
	cout<<"DO THI G BAN DAU:"<<endl;
	in_do_thi(G);
	cout<<"CAY KHUNG T BANG THUAT TOAN PRIM:"<<endl;
	if (tt_prim(G,T)==0) cout<<"Do thi ko lien thong";
	else
	{
		in_do_thi(T);	
		cout<<"Trong so cua T la: "<<tong_tso(T)<<endl;
	}
    return 1;
}